package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/6 16:59
 * @Describe “盛最多水的容器”是一个经典的算法问题。给定一个整数数组 height，
 * 其中每个元素代表柱子的高度，求能盛水的最大容器的容量。
 *
 * 给定 n 个非负整数 a1, a2, …, an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 问题分析
 * 可以使用双指针法来解决这个问题：
 *
 * 初始化两个指针，分别指向数组的两端。
 * 计算当前容器的容量，即 min(height[left], height[right]) * (right - left)，其中 left 和 right 是两个指针。
 * 更新最大容量的值。
 * 根据高度移动指针：如果 height[left] < height[right]，则移动 left 指针；否则移动 right 指针。
 * 重复以上步骤，直到两个指针相遇。
 */
public class MaxArea {
    public int maxArea(int[] height) {
        int maxArea = 0;  // 用于存储最大面积
        int left = 0;     // 左指针
        int right = height.length - 1; // 右指针

        while (left < right) {
            // 计算当前容器的面积
            int currentHeight = Math.min(height[left], height[right]);
            int width = right - left;
            int currentArea = currentHeight * width;

            // 更新最大面积
            maxArea = Math.max(maxArea, currentArea);

            // 移动指针，选择更高的柱子
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;  // 返回最大面积
    }

    public static void main(String[] args) {
        MaxArea solution = new MaxArea();
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int result = solution.maxArea(height);
        System.out.println("最大盛水容器的容量是: " + result);
    }
}
